1. Field of the Invention
The present invention relates to a bandwidth management apparatus that outputs packets in accordance with the bandwidth set value predetermined for each packet destination.
2. Description of the Related Art
In layer 2 switches, etc., bandwidth management is performed in which packets are output by observing the bandwidth set value predetermined, for example, under a contract with a user, for each frame or packet destination (for example, the destination MAC address in the packet—hereinafter, frames and packets will be collectively referred to as packets).
In this bandwidth management, each arriving packet is stored in a designated one of a plurality of queues according to its destination, and the plurality of queues are sequentially referred to in accordance with a simple round robin scheme; then, if any packet is stored in the queue thus referred to, and if the bandwidth that would be used if the packet were transmitted out from that queue does not exceed the bandwidth set value, then the packets are transmitted out one by one. For this purpose, a token bucket is provided for each queue, and control is performed so that tokens equal in value to the bandwidth set value are added to the token bucket at predetermined update intervals, and so that, when transmitting out a packet, tokens equal in value to the packet length of the packet to be transmitted out are removed from it, with provisions made to permit the transmission of the packet when the tokens contained in the token bucket are larger in value than a predetermined threshold value. An upper limit is imposed to how many tokens can be accumulated in the token bucket while no packets are arriving; with this upper limit, the peak value of the bandwidth used is limited if, thereafter, packets arrive in bursts.
The threshold value is set, for example, to 0, which means that when the token value of the token bucket is positive, the packet is transmitted out. The upper limit value is usually set equal to the bandwidth set value×1; with this setting, since tokens are not accumulated beyond the bandwidth set value when no packets are arriving, if thereafter packets arrive in bursts, the packets can be output by observing the bandwidth set value.
FIG. 1 shows one example of control in the bandwidth management mode. Parts (a) to (c) show the arriving packets destined for #0, #1, and #2, respectively (i.e., the packets arriving at queues #0, #1, and #2, respectively), part (d) shows the token add time, part (e) shows the packets to be transmitted out, and parts (f) to (h) show the change in the amount of tokens in the token buckets (#0 to #2) corresponding to the respective destinations #0 to #2.
It is assumed that, by the token add time A, packets have arrived one for each of the queues #0 to #2, as indicated by reference character B. When tokens are added at the token add time A, and the token value of each token bucket therefore becomes positive (parts (f) to (h)), the packets are output in the order of #0, #1, and #2 (part (e)), and the token value of each token bucket is reduced by an amount equal to the packet length of the transmitted packet (parts (f) to (h)). As a result, the token value of each of the token buckets #0 to #2 becomes negative; therefore, if any packets arrive at the queues #0 to #2, the packets cannot be output until the next token add time arrives. At the next token add time C, tokens are added to each token bucket in accordance with the bandwidth set value, and thereafter, the packets (D) that have arrived by that time are sequentially output (part (e)). Here, by the time that the packet for #2 is output, the next packet (E) for #0 has already arrived and, since the token value of the token bucket #0 (part (f)) is positive, the packet for #0 is transmitted out following the transmission of the packet for #2.
In some cases, surplus bandwidth mode control may be performed in addition to the above bandwidth management control. In the bandwidth management mode, when the token value of the token bucket is below the threshold for all the queues in which packets are stored, packet output permissions cannot be granted until the next update time arrives; in such a case, in the surplus bandwidth mode, control is performed so that packet output permissions are granted to queues reserved for users contracted for the use of the surplus bandwidth.
FIG. 2 shows one example of control in the surplus bandwidth mode. As in the case of FIG. 1, when the packets B that arrived by the update time A are sequentially output (part (e)), the values of the token buckets #0 to #2 become negative (parts (f) to (h)). At this time, if a packet D arrives at the queue #0 contracted for the surplus bandwidth mode, the packet is output as shown in part (e′). In this case, no tokens are removed because the packet is output using the surplus bandwidth (part (f)).
FIG. 3 is a diagram for explaining a problem that can occur in the bandwidth management mode. Part (a) shows the token add time, part (b) shows the packets arriving at the queue #0, part (c) shows the packets output from the queues #0 to #2, and part (d) shows how the token value of the token bucket #0 changes. A dashed line extending horizontally in part (d) indicates the upper limit value of the token bucket, which is set equal to the bandwidth set value×1.
In FIG. 3, the packet E that has been stored in the queue by the update time A is output during an interval A-B between the update time A and the update time B. The packet F that has been stored by the update time B is output during an interval B-C. When the tokens equal in value to the bandwidth set value×1 are added at the update time B, any tokens exceeding the upper limit are discarded as shown by an arrow G in part (d), but this does not present any problem. The reason is that, in the interval A-B, the packet E was the only packet that had arrived at the queue #0 and was therefore able to be output during that interval, and the discarded bandwidth G is equal in value to the bandwidth G′, indicated by an arrow G′, which was not used in the interval A-B.
On the other hand, at the update time C also, the token value is truncated as shown by an arrow H, but this presents a problem. The reason is that, in the interval B-C, not only the packet F but other packets I, J, and K also arrived at the queue #0 (part (b)) but, as a long packet L was output from the queue #2 over the period extending beyond the update time C, the bandwidth H′ remained unused and the bandwidth H corresponding to it was discarded without being used. This means that the contracted bandwidth could not be provided because of the packet output from another queue.
One possible method to prevent this would be to increase the upper limit of the token bucket. In that case, however, tokens would be excessively accumulated while no packets were being input, eventually allowing bursts of packets to be output.
FIG. 4 is a diagram for explaining a first problem that can arise when the surplus bandwidth mode is permitted. In FIG. 4, part (a) shows the token add time, part (b) shows the packets output in the bandwidth management mode, and part (c) shows the packets output in the surplus bandwidth mode.
In the interval A-B, the packets in the queues #0 to #2 are output in the bandwidth management mode, and the token values of the token buckets #0 to #2 become negative; in this case, even if any packets remain in the queues #0 to #2, the packets cannot be output in the bandwidth management mode, but if the queues #0 to #2 are permitted to output the packets in the surplus bandwidth mode, then the packets are output sequentially in the surplus bandwidth mode, as shown in part (c). At this time, if the packet last output in the surplus bandwidth mode (in the example, the packet from the queue #2) is so long that it overlaps into the next interval B-C as shown by an arrow E, the start of the bandwidth management mode in the interval B-C will be correspondingly delayed. Then, the packet F in the queue #0, which should have normally been output during the interval B-C, will be output during the interval C-D, leading to the problem of improper token discarding as in the earlier described case.
FIG. 5 is a diagram for explaining a second problem that can arise when the surplus bandwidth mode is permitted. In FIG. 5, part (a) shows the packets output in the bandwidth management mode, and part (b) shows the packets output in the surplus bandwidth mode. As shown, packets of identical length are contained in the respective queues #0, #4, #5, and #7; assume here that the bandwidth set value for each of #0, #4, and #7 is set equal to a value that permits one packet to be output within each add interval, while for #5, it is set to a value that permits two packets to be output, and also assume that the use of the surplus bandwidth is permitted for all of #0, #4, #5, and #7, and that packets are input to each queue at a rate higher than the bandwidth set value. In this case, as can be seen from FIG. 5, the packet last output in the bandwidth management mode is always the packet from the queue #5 and, as a result, the packet first output in the surplus bandwidth mode is always the packet from the queue #7 that follows the queue #5. Further, the packet last output in the surplus bandwidth mode is always the packet from the queue #4 and, as a result, the packet first output in the bandwidth management mode is always the packet from the queue #5 that follows the queue #4. Therefore, the queue #5 is not selected in the surplus bandwidth mode, resulting in unfair scheduling between channels.
To further generalize, the queue (in the above example, #5) given the highest bandwidth set value of all the queues is highly likely to be scheduled to be output last in the bandwidth management mode, and as a result, the probability of the ensuing queue (in the above example, #7) being scheduled in the surplus bandwidth mode increases, thus resulting in unfair output scheduling.